#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

/*
	1. Reverse dfs, find post order of all nodes
	2. Sort nodes by post order
	3. Dfs in turn, each terminated dfs constructs a strong connected component

	Key: The node with maxim post order when running reversed DFS belongs to the sink component
*/

struct IVtxVisitor
{
	virtual void Visit(int vertexid)=0;
};
struct Context
{
	IVtxVisitor *preVis, *postVis;
	vector<int> visited;
	vector<int> postid;
	int postid_max;
	Context(int N, IVtxVisitor *preVis=NULL, IVtxVisitor *postVis=NULL)
		:  visited(N), postid(N), postid_max(0),
		preVis(preVis), postVis(postVis)
	{}
};
struct Vertex_PostID
{
	int vertexid, postid;
	Vertex_PostID(int vertexid=0,int postid=0)
	{
		this->vertexid=vertexid;
		this->postid=postid;
	}
	bool operator<(const Vertex_PostID& vp)
	{
		return postid>vp.postid; // reverse it, so sorted by postid desc
	}
};
inline bool strong_connected_component_test_reachable(int v)
{
#pragma message ("!!! Please make sure the method <strong_connected_component_test_reachable> reflects your logic")
	const int INF=0xFFFFF;
	return v<INF;
}
template <typename T>
void dfs(int N, T g, int s, Context& ctx, bool brev=false)
{
	if(ctx.visited[s])
		return;

	ctx.visited[s]=1;
	if(ctx.preVis) ctx.preVis->Visit(s);
	
	for(int i=0;i<N;i++)
	{
		int v=brev ? g[i][s] : g[s][i];
		if(strong_connected_component_test_reachable(v))
		{
			dfs(N, g, i, ctx, brev);
		}
	}
	ctx.postid[s]=ctx.postid_max++;
	if(ctx.postVis) ctx.postVis->Visit(s);
}

struct VtxCollector : public IVtxVisitor
{
	vector<int> vtxes;
	void Visit(int vertexid)
	{
		vtxes.push_back(vertexid);
	}
};

template <typename T>
vector<vector<int> > strong_connected_component(int N, T g)
{
	Context ctx(N);
	for(int i=0;i<N;i++)
		dfs(N, g, i, ctx, true);
	
	vector<Vertex_PostID> vvp;
	for(int i=0;i<N;i++)
		vvp.push_back(Vertex_PostID(i, ctx.postid[i]));
	sort(vvp.begin(), vvp.end());
	
	vector<vector<int> > ret;
	
	VtxCollector col;
	Context ctx2(N, &col);
	for(int i=0;i<N;i++)
	{
		int s=vvp[i].vertexid;
		if(!ctx2.visited[s])
		{
			col.vtxes.resize(0);
			dfs(N, g, s, ctx2);
			ret.push_back(col.vtxes);
		}
	}
	return ret;
}

int main()
{

	const int N=3;
	int d[N][N]=
	{
		0,2,6,
		2,0,3,
		6,3,0,
	};

	vector<vector<int> > ret=strong_connected_component(N, d); // (0,1,2)

	const int INF=0xFFFFF;
	int d2[N][N]=
	{
		0,2,6,
		INF,0,3,
		INF,INF,0,
	};
	vector<vector<int> > ret2=strong_connected_component(N, d2); // (0), (1), (2)

	int d3[N][N]=
	{
		0,2,6,
		INF,0,3,
		INF,3,0,
	};
	vector<vector<int> > ret3=strong_connected_component(N, d3); // (0), (1,2)

	{
		const int nn=6;
		int d[nn][nn]=
		{
			0, 1,INF,1, INF,INF,
			INF, 0,1,INF, INF,1,
			INF, 1,0,INF, INF,INF,
			INF, INF,INF,0, 1,1,
			INF, INF,INF,1, 0,INF,
			INF, INF,INF,INF, INF,0,
		};

		vector<vector<int> > ret=strong_connected_component(nn, d); // (0,1,2)
	}
}